package mathMethod;

import java.util.Random;

public class MinMoves2 {

    private static Random random = new Random();

    /**
     * LeetCode T462 最少移动次数使数组元素相等
     * @param args
     */
    public static void main(String[] args) {

    }

    public int minMoves2(int[] nums) {
        int len = nums.length;
        int target;
        int ans = 0;
        if (len % 2 == 1){
            target =  quickSelect(nums, 0, len - 1, len/2);
        } else {
            target = (quickSelect(nums, 0, len - 1,len/2) + quickSelect(nums, 0, len - 1, len/2 - 1))/2;
        }
        for (int i = 0; i < len; i++){
            ans += (Math.abs(nums[i] - target));
        }
        return ans;
    }

    //使用快排找到中位数
    public int quickSelect(int[] nums, int left, int right, int index){
        int i = partition(nums, left, right);
        if (i == index){
            return nums[i];
        }

        return i > index ? quickSelect(nums, left, i - 1, index):quickSelect(nums, i + 1, right, index);

    }

    //获得坐标
    public int partition(int[] nums, int left, int right){
        //得到坐标
        int i = random.nextInt(right - left + 1) + left;
        swap(nums, i, right);
        int key = nums[right];
        int index = left - 1;
        for (int j = left; j < right; j++){
            if (nums[j] < key){
                swap(nums, ++index, j);
            }
        }
        swap(nums, index + 1, right);
        return index + 1;

    }

    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
